package sort;
/**
 * 什么是堆结构?
 * 如果按照从小到大的顺序排序，要求非叶结点的数据要大于或等于其左右结点的数据。
 * 如果按照从大到小的顺序排序，要求非叶结点的数据要小于等于其左右结点的数据
 *1.父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。
 *2.每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。
 * 一般都用数组来表示堆，i结点的父结点下标就为(i – 1) / 2。
 * 它的左右子结点下标分别为2 * i + 1和2 * i + 2。如第0个结点左右子结点下标分别为1和2。
 *
 *
 */

/**
 *  一个完整的堆排序需要经过反复的两个步骤:
 *  构造堆和堆排序输出
 *  ---构造堆结构就是把原始的无序元素按前面堆结构的定义进行调整。
 *  首先将原始的无序数据放置到一个完全二叉树的各个结点中，。
 *  然后，由完全二叉树的下层向上层逐层进行父子结点的数据进行比较，使父结点的数据
 *  大于子结点的数据。这里需要使用”筛" 运算进行结点数据的调整，
 *  直到使所有结点最后满足堆结构的条件位置，
 *  筛运算主要针对非叶结点进行调整。
 */
public class HeapSort {

    public static void main(String[] args){
        heapSort(new int[]{5,4,3,2,1,2,3,4,5},9);
    }
    public static void heapSort(int arr[],int n){
        int j;
        for(int i=n/2-1;i>=0;i--){ //将a[0,n-1]建成大根堆
            while(2*i+1<n){   //第i个结点有有右子树
                j=2*i+1;
                if((j+1)<n){
                    if(arr[j]<arr[j+1]){ //右左子树小于右子树，则需要比较右子树
                        j++;          //序号增加1，指向右子树
                    }
                }
                if(arr[i]<arr[j]){
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                    i = j;
                }else{
                    break;
                }
            }
        }
        //输出构成的堆
        System.out.println("原数据构成的堆");
        for(int h=0;h<n;h++){
            System.out.print(" "+arr[h]);
        }
        System.out.println();
        for(int i=n-1;i>0;i--){
            int temp = arr[0];//与第i个记录交换
            arr[0]=arr[i];
            arr[i]=temp;
            int k=0;
            while(2*k+1<i){//第i个结点有右子树
                j=2*k+1;
                if((j+1)<i){
                    if(arr[j]<arr[j+1]){//右左子树小于右子树,则需要比较右子树
                        j++;        //需要增加1，指向右子树
                    }
                }
                if(arr[k]<arr[j]){  //比较i与j为序号的数据
                    temp = arr[k];  //交换数据
                    arr[k] = arr[j];
                    arr[j]=temp;
                    k=j;                 //堆被破坏需要重新调整
                }else{  //比较左右子结点均大则堆未被破坏，不需要调整
                    break;
                }
            }
            System.out.println("第"+(n-i)+"步排序结果:");//输出每步排序的结果
            for(int h=0;h<n;h++){
                System.out.println(" "+arr[h]);
            }
            System.out.println();
        }
    }
}
